package Top_Interview_Questions_Review._003BFS;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/7 16:41
 * <p>
 * https://leetcode-cn.com/problems/course-schedule/solution/tuo-bu-pai-xu-by-liweiwei1419/
 * https://leetcode-cn.com/problems/course-schedule/solution/course-schedule-tuo-bu-pai-xu-bfsdfsliang-chong-fa/
 * 上面两个题解综合着看
 */
public class _0207 {

    public static void main(String[] args) {
        _0207 test = new _0207();
        int numCourses = 4;
        int[][] prerequisites = {{1,0},{2,0},{3,1},{3,2}};
        test.canFinish(numCourses,prerequisites);
    }

    //这个方法属于BFS,因为是按宽度搜的,不是从一个节点一直搜到根
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return false;
        }

        // 特判
        int pLen = prerequisites.length;
        if (pLen == 0) {
            return true;
        }

        //入度表
        int[] inDegree = new int[numCourses];
        //领接表
        HashSet<Integer>[] adj = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new HashSet<>();
        }

        //同时构造邻接表和入度表   {{1,0},{2,0},{3,1},{3,2}};
        for (int[] p : prerequisites) {
            inDegree[p[0]]++;
            adj[p[1]].add(p[0]);
        }

        Queue<Integer> queue = new LinkedList<>();

        // 首先加入入度为 0 的结点
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        // 记录已经出队的课程数量
        int cnt = 0;
        while (!queue.isEmpty()) {
            Integer top = queue.poll();

            cnt += 1;
            // 遍历当前出队结点的所有后继结点
            for (int successor : adj[top]) {
                inDegree[successor]--;
                if (inDegree[successor] == 0) {
                    queue.add(successor);
                }
            }
        }
        return cnt == numCourses;
    }

}
